1. Field of the Invention
The present invention relates generally to computer-aided design, manufacture and engineering, and more particularly to a system and method for improved solid object modelling.
2. Description of the Related Art
Boundary representations (b-reps) and constructive solid geometry (CSG) are the two most widely used representation schemes for solids. Properties of CSG representations are summarized in Requicha, A. A. G., and Voelcker, H. B. Constructive Solid Geometry. Tech. Memo 25, Production Automation Project, Univ. of Rochester, Rochester, N.Y., 1977. Central to CSG are notions of closed-set regularity and regularization relative to the topology of the Euclidean space. Regularization of a set X is defined by kiX, where k and i denote, respectively, operations of closure and interior. Regularized set operations .andgate.* and .orgate.*, and -* are defined by regularizing the results of the corresponding standard set operations and have the effect of always producing homogeneously "solid" sets. Properties of closed regular sets have been studied in Kuratowski, K., and Mostowski, A. Set Theory. North-Holland, Amsterdam, 1976, as well as McKinsey, J. C. C., and Tarski, A. On closed elements in closure algebras. Ann. Math. 47, 1 (Jan. 1946), pp. 122-162, and Requicha et al. Constructive Solid Geometry, supra., and are well understood.
While the problem of computing a B-rep (FIG. 1c) from a CSG representation (FIG. 1b) for an example solid (FIG. 1a) is relatively well understood, the inverse problem of B-rep to CSG conversion has not been addressed in general. Important applications of b-rep to CSG conversion arise in a variety of fields, including solid modeling and image processing.
The importance of b-rep to CSG conversion can be seen from the following considerations:
Both of these types of systems are useful when writing production applications for manufacturing or engineering. Depending on the problem one is trying to solve, one may want to represent a solid either as a b-rep or as constructive solid geometry; therefore, having conversions between the two is extremely useful. PA1 The inability to perform b-rep to CSG conversion puts significant constraints on the design of modern solid modelling systems such as a true dual representation architecture of a solid modelling system that allows representation-specific technology to be used on alternative representations through a bilateral b-rep-CSG conversion.
One of the difficult aspects of the b-rep to CSG conversion problem is that the boundary representation of an object is unique. On the other hand, the CSG representation or solution is not unique; there are an infinite number of solutions in CSG for the same b-rep. Moreover, until now there has been no viable solution to the problem for curved three-dimensional solid objects.